package algorithm.tree;

public class BinarySearchTree<E extends Comparable<? super E>> {
	private BinaryNode<E> root;
	private int nodeCount = 0;
	public BinarySearchTree(){
		root = null;
		nodeCount = 0;
	}
	
	public int getNodeCount(){
		return nodeCount;
	}
	public void makeEmpty(){
		root = null;
		nodeCount = 0;
	}
	
	public boolean isEmpty(){
		return root == null;
	}
	
	public boolean contains(E elem){
		return contains(elem, root);
	}
	
	private boolean contains(E elem, BinaryNode<E> node){
		if(node == null)
			return false;
		int compareResult = elem.compareTo(node.element);
		if(compareResult < 0)
			return contains(elem, node.left);
		else if(compareResult > 0)
			return contains(elem, node.right);
		else
			return true;
	}
	
	public E findMin(){
		return findMin(root).element;
	}
	
	private BinaryNode<E> findMin(BinaryNode<E> elem){
		if(elem == null)
			return null;
		else if(elem.left == null)
			return elem;
		return findMin(elem.left);
	}
	
	public E findMax(){
		return findMax(root).element;
	}
	
	private BinaryNode<E> findMax(BinaryNode<E> elem){
		if(elem != null)
			while(elem.right != null)
				elem = elem.right;
		return elem;
	}
	
	public void insert(E x){
		root = insert(x, root);
		nodeCount++;
	}
	
	private BinaryNode<E> insert(E elem, BinaryNode<E> node){
		if(node == null)
			return new BinaryNode<E>(elem, null, null);
		int compareResult = elem.compareTo(node.element);
		if(compareResult < 0)
			node.left = insert(elem, node.left);
		else if(compareResult > 0)
			node.right = insert(elem, node.right);
		else
			;
		return node;
	}
	
	public void remove(E elem){
		root = remove(elem, root);
	}
	
	private BinaryNode<E> remove(E elem, BinaryNode<E> node){
		if(node == null){
			return node;
		}
		int compareResult = elem.compareTo(node.element);
		
		if(compareResult < 0){
			node.left = remove(elem, node.left);
		}
		else if(compareResult > 0)
			node.right = remove(elem, node.right);
		else if(node.left != null && node.right != null){
			node.element = findMin(node.right).element;
			node.right = remove(node.element, node.right);
		}
		else
			node = (node.left != null) ? node.left : node.right;
		
		return node;
	}
	
	public void printTreeFirstRoot(){
		if(isEmpty())
			System.out.println("Empty tree!");
		else
			printTreeFirstRoot(root);
	}
	private void printTreeFirstRoot(BinaryNode<E> node){
		if(node != null){
			System.out.print(node.element + " ");
			printTreeFirstRoot(node.left);
			printTreeFirstRoot(node.right);
		}
	}
	
	public void printTreeMidRoot(){
		if(isEmpty())
			System.out.println("Empty tree!");
		else
			printTreeMidRoot(root);
	}
	private void printTreeMidRoot(BinaryNode<E> node){
		if(node != null){
			printTreeMidRoot(node.left);
			System.out.print(node.element + " ");
			printTreeMidRoot(node.right);
		}
	}
	
	public void printTreeLastRoot(){
		if(isEmpty())
			System.out.println("Empty tree!");
		else
			printTreeLastRoot(root);
	}
	private void printTreeLastRoot(BinaryNode<E> node){
		if(node != null){
			printTreeLastRoot(node.left);
			printTreeLastRoot(node.right);
			System.out.print(node.element + " ");
		}
	}
}
